package com.leetcode.algorithm.y22.m06;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 45. 跳跃游戏 II
 * 
 * https://leetcode.cn/problems/jump-game-ii/
 * 
 * @author jie.deng
 *
 */
class Question0045Solution02 {

	/**
	 * BFS
	 * 
	 * @param nums
	 * @return
	 */
	public int jump(int[] nums) {
		int len = nums.length;
		if (len == 1) {
			return 0;
		}
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[len];
		int step = 0;

		// 状态初始化
		visited[0] = true;
		queue.add(0);

		while (!queue.isEmpty()) {
			// 当前层可达的节点
			step++;
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				// 下一层可达的节点
				int curIdx = queue.poll().intValue();
				for (int j = 0; j <= nums[curIdx] && curIdx + j < len; j++) {
					if (!visited[curIdx + j]) {
						visited[curIdx + j] = true;
						queue.add(curIdx + j);
					}
				}
			}
		}

		return step - 1;
	}

}